package com.wuyou.mid;

/**
 * 验证栈序列
 */
public class ValidateStackSequences {

    public static void main(String[] args) {
        ValidateStackSequences v = new ValidateStackSequences();
        int[] pushed = {2, 1, 0};
        int[] popped = {1, 2, 0};
//        int[] pushed = {0, 1};
//        int[] popped = {1, 0};
//        int[] pushed = {4, 0, 3, 1, 2};
//        int[] popped = {3, 1, 0, 2, 4};
//        int[] pushed = {1, 2, 3, 4, 5};
//        int[] popped = {4, 3, 5, 1, 2};

        System.out.println(v.solution_1(pushed, popped));
    }

    public boolean solution_1(int[] pushed, int[] popped) {

        int right = 0;
        int left = 0;
        while (left >= 0 && left < pushed.length && right < popped.length) {
            if (pushed[left] != popped[right]) {
                left++;
            } else if (pushed[left] == popped[right]) {
                pushed[left] = -1;
                right++;
                while (left > 0 && right < popped.length) {
                    left--;
                    if (pushed[left] == -1) {
                        continue;
                    } else {
                        if (pushed[left] == popped[right]) {
                            right++;
                            pushed[left] = -1;
                        } else {
                            break;
                        }
                    }
                }
            }
        }
        return right == popped.length;
    }
}